package com.ryujung.linked_list.leetCode_53;

/*
 * @lc app=leetcode.cn id=53 lang=java
 *
 * [53] 最大子序和
 *
 * https://leetcode-cn.com/problems/maximum-subarray/description/
 *
 * algorithms
 * Easy (50.28%)
 * Likes:    1879
 * Dislikes: 0
 * Total Accepted:    213.7K
 * Total Submissions: 424.5K
 * Testcase Example:  '[-2,1,-3,4,-1,2,1,-5,4]'
 *
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 
 * 示例:
 * 
 * 输入: [-2,1,-3,4,-1,2,1,-5,4],
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * 
 * 
 * 进阶:
 * 
 * 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
 * 
 */

// @lc code=start
class Solution {
    /**
     * 动态规划的正常做法
     * dp[i] 代表nums数组的前i个元素的最大子序和
     * dp[0]代表nums为空的子序和，为0
     * 由于题目给定子序最少包含一个元素，dp[0]不能作为最终结果的初始值
     * 因为有可能所有元素都是负数，即res也为负数，不是0
     * 
     * 将res初始化为数组第一个元素nums[0]即可
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;

        int res = nums[0];

        for (int i = 1; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], 0) + nums[i - 1];
            res = Math.max(dp[i], res);
        }

        return res;
    }

    /**
     * 在动态规划的基础上进行空间优化，不使用dp数组，使用一个变量记录当前的最大子序和
     */
    public int maxSubArrayPlus(int[] nums) {
        int res = nums[0];
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            //如果当前选取的子序和+当前元素 < 直接选取当前元素，
            //就舍弃之前的子序和，直接选取当前元素重新累加
            sum = Math.max(sum + nums[i], nums[i]);
            res = Math.max(sum, res);//res始终记录所有情况中的最大值
        }

        return res;
    }

    /**
     * 在空间优化基础上将循环方式进行优化，使用foreach
     */
    public int maxSubArrayPPlus(int[] nums) {
        int res = nums[0];
        int sum = 0;

        for (int num : nums) {
            //如果当前选取的子序和+当前元素 < 直接选取当前元素，
            //就舍弃之前的子序和，直接选取当前元素重新累加
            sum = Math.max(sum + num, num);
            res = Math.max(sum, res);
        }

        return res;
    }

    /**
     * 动态规划的空间优化
     * 做法：
     * 1.定义最大子序和，即最终的结果res，初始化为nums的第一个数字即可，例如nums[0]
     * 2.定义当前选取子序列的益值sum，
     */
    public int maxSubArray4(int[] nums) {
        int res = nums[0];

        int sum = 0;

        for (int num : nums) {
            if (sum > 0) {
                //增益>0,继续累加
                sum += num;
            } else {
                //sum小于等于0，重新选择子序列为当前的num，直到sum值>0
                sum = num;
            }
            //每次sum更新时，记录当前的res和sum中的最大值
            res = Math.max(res, sum);
        }
        return res;
    }

    /**
     * 分治法求解
     * TODO
     */
    public int maxSubArray2(int[] nums) {
        int max = helper(nums, 0, nums.length);
        return 0;
    }

    /**
     * 分治法求解的辅助方法，用于获取nums数组中l~r范围内的最大值
     * 基本思路：分治递归
     * TODO
     */
    private int helper(int[] nums, int l, int r) {

        return 0;
    }

    /**
     * 暴力动态规划可以算出来，但是占用空间过大，无法通过测试
     * Time: O(n^2)
     * Space:O(n^2)
     */
    public int maxSubArray3(int[] nums) {
        int l = nums.length;

        int[][] dp = new int[l][l];

        int max = nums[0];
        for (int i = 0; i < l; i++) {
            dp[i][i] = nums[i];
            max = Math.max(max, dp[i][i]);
        }

        for (int i = 0; i < l; i++) {
            for (int j = i + 1; j < l; j++) {
                dp[i][j] = dp[i][j - 1] + nums[j];
                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        // int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int[] nums = { -2, 1 };
        System.out.println(s.maxSubArray(nums));
    }
}
// @lc code=end
